#include <iostream>
using namespace std;

struct node
{ int info;
  node *next;
};

struct List
{ node *first;
  node *last;
};
   
void push_front(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = L.first;
  if(L.first==NULL) L.first=L.last=t;
  else L.first = t;
}   
  
void push_back(List &L, int x)
{ node *t = new node;
  t->info = x;
  t->next = NULL;
  if(L.last==NULL) L.first=L.last=t;
  else { L.last->next = t; L.last=t;  }  
}

void append(List &L, node *p)
{ if(L.last==NULL){ L.first=L.last=p;}
  else { L.last->next = p; L.last=p;  }  
}

void append(List &L1, List L2)
{ if(L1.last==NULL){ L1.first=L2.first; L1.last=L2.last; }
  else { L1.last->next = L2.first; L1.last=L2.last;  }  
}

void show_list(List L)
{ node *p=L.first;
  while(p!=NULL)
  { cout << p->info << " ";
    p = p->next;
  }
  cout << endl;
}    

void split(List R, List &L1, List &L2)
{ L1.first=L1.last=L2.first=L2.last=NULL;
  int dir=1; node *p=R.first; 
  while(p!=NULL)
    if(dir==1)
    { append(L1,p); p = p->next; dir=2; }
    else
    { append(L2,p); p = p->next; dir=1; }
  L1.last->next = NULL;
  L2.last->next = NULL;
}



void merge(List L1, List L2, List &R)
{ R.first=R.last=NULL;
  node *p=L1.first, *q=L2.first; 
  while(p!=NULL && q!=NULL)
  { if(p->info <= q->info)
    { append(R,p); p = p->next; }
    else
    { append(R,q); q = q->next; }
  }   
    
  while(p!=NULL)
  { append(R,p); p = p->next; }
    
  while(q!=NULL)
  { append(R,q); q = q->next; }
}

void merge_sort(List &R)
{
  if(R.first != R.last) 
  { List L1, L2;
    split(R,L1,L2);
    merge_sort(L1);
    merge_sort(L2);
    merge(L1,L2,R);
  }
}

int main()
{ List R;

  R.first=R.last=NULL;
  
  push_back(R,50);
  push_back(R,40);
  push_back(R,56);
  push_back(R,34);
  push_back(R,45);
  push_back(R,30);
  push_back(R,20);
  
  show_list(R);
   
  merge_sort(R);
  
  show_list(R);
     
  return 0;
}    
